package ru.amse.stroganova.algorythms;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import ru.amse.stroganova.graph.AbstractGraph;
import ru.amse.stroganova.graph.Edge;
import ru.amse.stroganova.graph.Vertex;

/**
 * Presents minimal spanning tree search with Prime algorythm.
 * 
 * @author Dasha Stroganova
 *
 */
public class MinimalSpanningTree {

	//TODO may be error messages should be in actions not in algorythms.
	private static final String ERROR_MESSAGE = "Cannot find minimal spanning tree of the given graph - it is not connected.";
	
	private final boolean isConnected;
	
	private final List<Edge> tree;
	
	/**
	 * Creates new minimal spanning tree sort on this graph.
	 * 
	 * @param graph
	 */
	public MinimalSpanningTree(AbstractGraph graph) {
		List<Vertex> vertices = new ArrayList<Vertex>(graph.getVertices());
		Vertex[] predecessor = new Vertex[vertices.size()];
		BinaryHeap<Vertex, Integer> heap = new BinaryHeap<Vertex, Integer>();
		Set<Vertex> visitedVertices = new HashSet<Vertex>();
		
		for (Vertex vertex : graph.getVertices()) {
			heap.insert(vertex, Integer.MAX_VALUE);
		}
		
		heap.decreaseKey(vertices.get(0), 0);
		
		for (int i = 0; i < vertices.size(); i++) {
			Vertex vertex = heap.extractMin();
			visitedVertices.add(vertex);
			for (Edge edge : vertex.getOutgoingEdges()) {
				Vertex opposite = edge.getOppositeVertex(vertex);
				if (!visitedVertices.contains(opposite) && (heap.getKey(opposite) > edge.getWeight())) {//(keys[oppositeIndex] > edge.getWeight())) {
					heap.decreaseKey(opposite, edge.getWeight());
					predecessor[vertices.indexOf(opposite)] = vertex;
				}
			}
		}

		tree = new ArrayList<Edge>();
		for (int i = 1; i < predecessor.length; i++) {
			if (predecessor[i] != null) {
				tree.add(graph.getConnectingEdge(predecessor[i], vertices.get(i)));
			}
		}

		isConnected = (tree.size() == vertices.size() - 1);
	}

	
	/**
	 * Checks whether graph is connected.
	 * 
	 * @return true if it is; false otherwise
	 */
	public boolean isConnected() {
		return isConnected;
	}
	
	/**
	 * Returns list of tree edges if graph is connected. Throws IllegalStateException otherwise.
	 * 
	 * @return list of tree edges if graph is connected
	 */
	public List<Edge> getTreeEdges() {
		if (!isConnected()) {
			throw new IllegalStateException("Graph has no mst: it is not connected");
		}
		return tree;
	}
	
	/**
	 * If any errors exist return error message.
	 * 
	 * @return error message if error exists; empty string otherwise
	 */
	public String getErrorMessage() {
		return !isConnected() ? ERROR_MESSAGE : "";
	}
	
}
